// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2018-2019 Gael Guennebaud <gael.guennebaud@inria.fr>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

#include "main.h"
#include <iterator>
#include <numeric>

template<class Iterator>
std::reverse_iterator<Iterator>
make_reverse_iterator(Iterator i)
{
	return std::reverse_iterator<Iterator>(i);
}

#if !EIGEN_HAS_CXX11
template<class ForwardIt>
ForwardIt
is_sorted_until(ForwardIt firstIt, ForwardIt lastIt)
{
	if (firstIt != lastIt) {
		ForwardIt next = firstIt;
		while (++next != lastIt) {
			if (*next < *firstIt)
				return next;
			firstIt = next;
		}
	}
	return lastIt;
}
template<class ForwardIt>
bool
is_sorted(ForwardIt firstIt, ForwardIt lastIt)
{
	return ::is_sorted_until(firstIt, lastIt) == lastIt;
}
#else
using std::is_sorted;
#endif

template<typename XprType>
bool
is_pointer_based_stl_iterator(const internal::pointer_based_stl_iterator<XprType>&)
{
	return true;
}

template<typename XprType>
bool
is_generic_randaccess_stl_iterator(const internal::generic_randaccess_stl_iterator<XprType>&)
{
	return true;
}

template<typename Iter>
bool
is_default_constructible_and_assignable(const Iter& it)
{
#if EIGEN_HAS_CXX11
	VERIFY(std::is_default_constructible<Iter>::value);
	VERIFY(std::is_nothrow_default_constructible<Iter>::value);
#endif
	Iter it2;
	it2 = it;
	return (it == it2);
}

template<typename Xpr>
void
check_begin_end_for_loop(Xpr xpr)
{
	const Xpr& cxpr(xpr);
	Index i = 0;

	i = 0;
	for (typename Xpr::iterator it = xpr.begin(); it != xpr.end(); ++it) {
		VERIFY_IS_EQUAL(*it, xpr[i++]);
	}

	i = 0;
	for (typename Xpr::const_iterator it = xpr.cbegin(); it != xpr.cend(); ++it) {
		VERIFY_IS_EQUAL(*it, xpr[i++]);
	}

	i = 0;
	for (typename Xpr::const_iterator it = cxpr.begin(); it != cxpr.end(); ++it) {
		VERIFY_IS_EQUAL(*it, xpr[i++]);
	}

	i = 0;
	for (typename Xpr::const_iterator it = xpr.begin(); it != xpr.end(); ++it) {
		VERIFY_IS_EQUAL(*it, xpr[i++]);
	}

	{
		// simple API check
		typename Xpr::const_iterator cit = xpr.begin();
		cit = xpr.cbegin();

#if EIGEN_HAS_CXX11
		auto tmp1 = xpr.begin();
		VERIFY(tmp1 == xpr.begin());
		auto tmp2 = xpr.cbegin();
		VERIFY(tmp2 == xpr.cbegin());
#endif
	}

	VERIFY(xpr.end() - xpr.begin() == xpr.size());
	VERIFY(xpr.cend() - xpr.begin() == xpr.size());
	VERIFY(xpr.end() - xpr.cbegin() == xpr.size());
	VERIFY(xpr.cend() - xpr.cbegin() == xpr.size());

	if (xpr.size() > 0) {
		VERIFY(xpr.begin() != xpr.end());
		VERIFY(xpr.begin() < xpr.end());
		VERIFY(xpr.begin() <= xpr.end());
		VERIFY(!(xpr.begin() == xpr.end()));
		VERIFY(!(xpr.begin() > xpr.end()));
		VERIFY(!(xpr.begin() >= xpr.end()));

		VERIFY(xpr.cbegin() != xpr.end());
		VERIFY(xpr.cbegin() < xpr.end());
		VERIFY(xpr.cbegin() <= xpr.end());
		VERIFY(!(xpr.cbegin() == xpr.end()));
		VERIFY(!(xpr.cbegin() > xpr.end()));
		VERIFY(!(xpr.cbegin() >= xpr.end()));

		VERIFY(xpr.begin() != xpr.cend());
		VERIFY(xpr.begin() < xpr.cend());
		VERIFY(xpr.begin() <= xpr.cend());
		VERIFY(!(xpr.begin() == xpr.cend()));
		VERIFY(!(xpr.begin() > xpr.cend()));
		VERIFY(!(xpr.begin() >= xpr.cend()));
	}
}

template<typename Scalar, int Rows, int Cols>
void
test_stl_iterators(int rows = Rows, int cols = Cols)
{
	typedef Matrix<Scalar, Rows, 1> VectorType;
#if EIGEN_HAS_CXX11
	typedef Matrix<Scalar, 1, Cols> RowVectorType;
#endif
	typedef Matrix<Scalar, Rows, Cols, ColMajor> ColMatrixType;
	typedef Matrix<Scalar, Rows, Cols, RowMajor> RowMatrixType;
	VectorType v = VectorType::Random(rows);
	const VectorType& cv(v);
	ColMatrixType A = ColMatrixType::Random(rows, cols);
	const ColMatrixType& cA(A);
	RowMatrixType B = RowMatrixType::Random(rows, cols);

	Index i, j;

	// Verify that iterators are default constructible (See bug #1900)
	{
		VERIFY(is_default_constructible_and_assignable(v.begin()));
		VERIFY(is_default_constructible_and_assignable(v.end()));
		VERIFY(is_default_constructible_and_assignable(cv.begin()));
		VERIFY(is_default_constructible_and_assignable(cv.end()));

		VERIFY(is_default_constructible_and_assignable(A.row(0).begin()));
		VERIFY(is_default_constructible_and_assignable(A.row(0).end()));
		VERIFY(is_default_constructible_and_assignable(cA.row(0).begin()));
		VERIFY(is_default_constructible_and_assignable(cA.row(0).end()));

		VERIFY(is_default_constructible_and_assignable(B.row(0).begin()));
		VERIFY(is_default_constructible_and_assignable(B.row(0).end()));
	}

	// Check we got a fast pointer-based iterator when expected
	{
		VERIFY(is_pointer_based_stl_iterator(v.begin()));
		VERIFY(is_pointer_based_stl_iterator(v.end()));
		VERIFY(is_pointer_based_stl_iterator(cv.begin()));
		VERIFY(is_pointer_based_stl_iterator(cv.end()));

		j = internal::random<Index>(0, A.cols() - 1);
		VERIFY(is_pointer_based_stl_iterator(A.col(j).begin()));
		VERIFY(is_pointer_based_stl_iterator(A.col(j).end()));
		VERIFY(is_pointer_based_stl_iterator(cA.col(j).begin()));
		VERIFY(is_pointer_based_stl_iterator(cA.col(j).end()));

		i = internal::random<Index>(0, A.rows() - 1);
		VERIFY(is_pointer_based_stl_iterator(A.row(i).begin()));
		VERIFY(is_pointer_based_stl_iterator(A.row(i).end()));
		VERIFY(is_pointer_based_stl_iterator(cA.row(i).begin()));
		VERIFY(is_pointer_based_stl_iterator(cA.row(i).end()));

		VERIFY(is_pointer_based_stl_iterator(A.reshaped().begin()));
		VERIFY(is_pointer_based_stl_iterator(A.reshaped().end()));
		VERIFY(is_pointer_based_stl_iterator(cA.reshaped().begin()));
		VERIFY(is_pointer_based_stl_iterator(cA.reshaped().end()));

		VERIFY(is_pointer_based_stl_iterator(B.template reshaped<AutoOrder>().begin()));
		VERIFY(is_pointer_based_stl_iterator(B.template reshaped<AutoOrder>().end()));

		VERIFY(is_generic_randaccess_stl_iterator(A.template reshaped<RowMajor>().begin()));
		VERIFY(is_generic_randaccess_stl_iterator(A.template reshaped<RowMajor>().end()));
	}

	{
		check_begin_end_for_loop(v);
		check_begin_end_for_loop(A.col(internal::random<Index>(0, A.cols() - 1)));
		check_begin_end_for_loop(A.row(internal::random<Index>(0, A.rows() - 1)));
		check_begin_end_for_loop(v + v);
	}

#if EIGEN_HAS_CXX11
	// check swappable
	{
		using std::swap;
		// pointer-based
		{
			VectorType v_copy = v;
			auto a = v.begin();
			auto b = v.end() - 1;
			swap(a, b);
			VERIFY_IS_EQUAL(v, v_copy);
			VERIFY_IS_EQUAL(*b, *v.begin());
			VERIFY_IS_EQUAL(*b, v(0));
			VERIFY_IS_EQUAL(*a, v.end()[-1]);
			VERIFY_IS_EQUAL(*a, v(last));
		}

		// generic
		{
			RowMatrixType B_copy = B;
			auto Br = B.reshaped();
			auto a = Br.begin();
			auto b = Br.end() - 1;
			swap(a, b);
			VERIFY_IS_EQUAL(B, B_copy);
			VERIFY_IS_EQUAL(*b, *Br.begin());
			VERIFY_IS_EQUAL(*b, Br(0));
			VERIFY_IS_EQUAL(*a, Br.end()[-1]);
			VERIFY_IS_EQUAL(*a, Br(last));
		}
	}

	// check non-const iterator with for-range loops
	{
		i = 0;
		for (auto x : v) {
			VERIFY_IS_EQUAL(x, v[i++]);
		}

		j = internal::random<Index>(0, A.cols() - 1);
		i = 0;
		for (auto x : A.col(j)) {
			VERIFY_IS_EQUAL(x, A(i++, j));
		}

		i = 0;
		for (auto x : (v + A.col(j))) {
			VERIFY_IS_APPROX(x, v(i) + A(i, j));
			++i;
		}

		j = 0;
		i = internal::random<Index>(0, A.rows() - 1);
		for (auto x : A.row(i)) {
			VERIFY_IS_EQUAL(x, A(i, j++));
		}

		i = 0;
		for (auto x : A.reshaped()) {
			VERIFY_IS_EQUAL(x, A(i++));
		}
	}

	// same for const_iterator
	{
		i = 0;
		for (auto x : cv) {
			VERIFY_IS_EQUAL(x, v[i++]);
		}

		i = 0;
		for (auto x : cA.reshaped()) {
			VERIFY_IS_EQUAL(x, A(i++));
		}

		j = 0;
		i = internal::random<Index>(0, A.rows() - 1);
		for (auto x : cA.row(i)) {
			VERIFY_IS_EQUAL(x, A(i, j++));
		}
	}

	// check reshaped() on row-major
	{
		i = 0;
		Matrix<Scalar, Dynamic, Dynamic, ColMajor> Bc = B;
		for (auto x : B.reshaped()) {
			VERIFY_IS_EQUAL(x, Bc(i++));
		}
	}

	// check write access
	{
		VectorType w(v.size());
		i = 0;
		for (auto& x : w) {
			x = v(i++);
		}
		VERIFY_IS_EQUAL(v, w);
	}

	// check for dangling pointers
	{ // no dangling because pointer-based
	  { j = internal::random<Index>(0, A.cols() - 1);
	auto it = A.col(j).begin();
	for (i = 0; i < rows; ++i) {
		VERIFY_IS_EQUAL(it[i], A(i, j));
	}
}

// no dangling because pointer-based
{
	i = internal::random<Index>(0, A.rows() - 1);
	auto it = A.row(i).begin();
	for (j = 0; j < cols; ++j) {
		VERIFY_IS_EQUAL(it[j], A(i, j));
	}
}

{
	j = internal::random<Index>(0, A.cols() - 1);
	// this would produce a dangling pointer:
	// auto it = (A+2*A).col(j).begin();
	// we need to name the temporary expression:
	auto tmp = (A + 2 * A).col(j);
	auto it = tmp.begin();
	for (i = 0; i < rows; ++i) {
		VERIFY_IS_APPROX(it[i], 3 * A(i, j));
	}
}
}

{
	// check basic for loop on vector-wise iterators
	j = 0;
	for (auto it = A.colwise().cbegin(); it != A.colwise().cend(); ++it, ++j) {
		VERIFY_IS_APPROX(it->coeff(0), A(0, j));
		VERIFY_IS_APPROX((*it).coeff(0), A(0, j));
	}
	j = 0;
	for (auto it = A.colwise().begin(); it != A.colwise().end(); ++it, ++j) {
		(*it).coeffRef(0) = (*it).coeff(0); // compilation check
		it->coeffRef(0) = it->coeff(0);		// compilation check
		VERIFY_IS_APPROX(it->coeff(0), A(0, j));
		VERIFY_IS_APPROX((*it).coeff(0), A(0, j));
	}

	// check valuetype gives us a copy
	j = 0;
	for (auto it = A.colwise().cbegin(); it != A.colwise().cend(); ++it, ++j) {
		typename decltype(it)::value_type tmp = *it;
		VERIFY_IS_NOT_EQUAL(tmp.data(), it->data());
		VERIFY_IS_APPROX(tmp, A.col(j));
	}
}

#endif

if (rows >= 3) {
	VERIFY_IS_EQUAL((v.begin() + rows / 2)[1], v(rows / 2 + 1));

	VERIFY_IS_EQUAL((A.rowwise().begin() + rows / 2)[1], A.row(rows / 2 + 1));
}

if (cols >= 3) {
	VERIFY_IS_EQUAL((A.colwise().begin() + cols / 2)[1], A.col(cols / 2 + 1));
}

// check std::sort
{
	// first check that is_sorted returns false when required
	if (rows >= 2) {
		v(1) = v(0) - Scalar(1);
#if EIGEN_HAS_CXX11
		VERIFY(!is_sorted(std::begin(v), std::end(v)));
#else
			VERIFY(!is_sorted(v.cbegin(), v.cend()));
#endif
	}

	// on a vector
	{
		std::sort(v.begin(), v.end());
		VERIFY(is_sorted(v.begin(), v.end()));
		VERIFY(!::is_sorted(make_reverse_iterator(v.end()), make_reverse_iterator(v.begin())));
	}

	// on a column of a column-major matrix -> pointer-based iterator and default increment
	{
		j = internal::random<Index>(0, A.cols() - 1);
		// std::sort(begin(A.col(j)),end(A.col(j))); // does not compile because this returns const iterators
		typename ColMatrixType::ColXpr Acol = A.col(j);
		std::sort(Acol.begin(), Acol.end());
		VERIFY(is_sorted(Acol.cbegin(), Acol.cend()));
		A.setRandom();

		std::sort(A.col(j).begin(), A.col(j).end());
		VERIFY(is_sorted(A.col(j).cbegin(), A.col(j).cend()));
		A.setRandom();
	}

	// on a row of a rowmajor matrix -> pointer-based iterator and runtime increment
	{
		i = internal::random<Index>(0, A.rows() - 1);
		typename ColMatrixType::RowXpr Arow = A.row(i);
		VERIFY_IS_EQUAL(std::distance(Arow.begin(), Arow.end()), cols);
		std::sort(Arow.begin(), Arow.end());
		VERIFY(is_sorted(Arow.cbegin(), Arow.cend()));
		A.setRandom();

		std::sort(A.row(i).begin(), A.row(i).end());
		VERIFY(is_sorted(A.row(i).cbegin(), A.row(i).cend()));
		A.setRandom();
	}

	// with a generic iterator
	{
		Reshaped<RowMatrixType, RowMatrixType::SizeAtCompileTime, 1> B1 = B.reshaped();
		std::sort(B1.begin(), B1.end());
		VERIFY(is_sorted(B1.cbegin(), B1.cend()));
		B.setRandom();

		// assertion because nested expressions are different
		// std::sort(B.reshaped().begin(),B.reshaped().end());
		// VERIFY(is_sorted(B.reshaped().cbegin(),B.reshaped().cend()));
		// B.setRandom();
	}
}

// check with partial_sum
{
	j = internal::random<Index>(0, A.cols() - 1);
	typename ColMatrixType::ColXpr Acol = A.col(j);
	std::partial_sum(Acol.begin(), Acol.end(), v.begin());
	VERIFY_IS_APPROX(v(seq(1, last)), v(seq(0, last - 1)) + Acol(seq(1, last)));

	// inplace
	std::partial_sum(Acol.begin(), Acol.end(), Acol.begin());
	VERIFY_IS_APPROX(v, Acol);
}

// stress random access as required by std::nth_element
if (rows >= 3) {
	v.setRandom();
	VectorType v1 = v;
	std::sort(v1.begin(), v1.end());
	std::nth_element(v.begin(), v.begin() + rows / 2, v.end());
	VERIFY_IS_APPROX(v1(rows / 2), v(rows / 2));

	v.setRandom();
	v1 = v;
	std::sort(v1.begin() + rows / 2, v1.end());
	std::nth_element(v.begin() + rows / 2, v.begin() + rows / 4, v.end());
	VERIFY_IS_APPROX(v1(rows / 4), v(rows / 4));
}

#if EIGEN_HAS_CXX11
// check rows/cols iterators with range-for loops
{
	j = 0;
	for (auto c : A.colwise()) {
		VERIFY_IS_APPROX(c.sum(), A.col(j).sum());
		++j;
	}
	j = 0;
	for (auto c : B.colwise()) {
		VERIFY_IS_APPROX(c.sum(), B.col(j).sum());
		++j;
	}

	j = 0;
	for (auto c : B.colwise()) {
		i = 0;
		for (auto& x : c) {
			VERIFY_IS_EQUAL(x, B(i, j));
			x = A(i, j);
			++i;
		}
		++j;
	}
	VERIFY_IS_APPROX(A, B);
	B.setRandom();

	i = 0;
	for (auto r : A.rowwise()) {
		VERIFY_IS_APPROX(r.sum(), A.row(i).sum());
		++i;
	}
	i = 0;
	for (auto r : B.rowwise()) {
		VERIFY_IS_APPROX(r.sum(), B.row(i).sum());
		++i;
	}
}

// check rows/cols iterators with STL algorithms
{
	RowVectorType row = RowVectorType::Random(cols);
	A.rowwise() = row;
	VERIFY(std::all_of(A.rowwise().begin(), A.rowwise().end(), [&row](typename ColMatrixType::RowXpr x) {
		return internal::isApprox(x.squaredNorm(), row.squaredNorm());
	}));
	VERIFY(std::all_of(A.rowwise().rbegin(), A.rowwise().rend(), [&row](typename ColMatrixType::RowXpr x) {
		return internal::isApprox(x.squaredNorm(), row.squaredNorm());
	}));

	VectorType col = VectorType::Random(rows);
	A.colwise() = col;
	VERIFY(std::all_of(A.colwise().begin(), A.colwise().end(), [&col](typename ColMatrixType::ColXpr x) {
		return internal::isApprox(x.squaredNorm(), col.squaredNorm());
	}));
	VERIFY(std::all_of(A.colwise().rbegin(), A.colwise().rend(), [&col](typename ColMatrixType::ColXpr x) {
		return internal::isApprox(x.squaredNorm(), col.squaredNorm());
	}));
	VERIFY(std::all_of(A.colwise().cbegin(), A.colwise().cend(), [&col](typename ColMatrixType::ConstColXpr x) {
		return internal::isApprox(x.squaredNorm(), col.squaredNorm());
	}));
	VERIFY(std::all_of(A.colwise().crbegin(), A.colwise().crend(), [&col](typename ColMatrixType::ConstColXpr x) {
		return internal::isApprox(x.squaredNorm(), col.squaredNorm());
	}));

	i = internal::random<Index>(0, A.rows() - 1);
	A.setRandom();
	A.row(i).setZero();
	VERIFY_IS_EQUAL(std::find_if(A.rowwise().begin(),
								 A.rowwise().end(),
								 [](typename ColMatrixType::RowXpr x) { return x.squaredNorm() == Scalar(0); }) -
						A.rowwise().begin(),
					i);
	VERIFY_IS_EQUAL(std::find_if(A.rowwise().rbegin(),
								 A.rowwise().rend(),
								 [](typename ColMatrixType::RowXpr x) { return x.squaredNorm() == Scalar(0); }) -
						A.rowwise().rbegin(),
					(A.rows() - 1) - i);

	j = internal::random<Index>(0, A.cols() - 1);
	A.setRandom();
	A.col(j).setZero();
	VERIFY_IS_EQUAL(std::find_if(A.colwise().begin(),
								 A.colwise().end(),
								 [](typename ColMatrixType::ColXpr x) { return x.squaredNorm() == Scalar(0); }) -
						A.colwise().begin(),
					j);
	VERIFY_IS_EQUAL(std::find_if(A.colwise().rbegin(),
								 A.colwise().rend(),
								 [](typename ColMatrixType::ColXpr x) { return x.squaredNorm() == Scalar(0); }) -
						A.colwise().rbegin(),
					(A.cols() - 1) - j);
}

{
	using VecOp = VectorwiseOp<ArrayXXi, 0>;
	STATIC_CHECK((internal::is_same<VecOp::const_iterator, decltype(std::declval<const VecOp&>().cbegin())>::value));
	STATIC_CHECK((internal::is_same<VecOp::const_iterator, decltype(std::declval<const VecOp&>().cend())>::value));
#if EIGEN_COMP_CXXVER >= 14
	STATIC_CHECK(
		(internal::is_same<VecOp::const_iterator, decltype(std::cbegin(std::declval<const VecOp&>()))>::value));
	STATIC_CHECK((internal::is_same<VecOp::const_iterator, decltype(std::cend(std::declval<const VecOp&>()))>::value));
#endif
}

#endif
}

#if EIGEN_HAS_CXX11
// When the compiler sees expression IsContainerTest<C>(0), if C is an
// STL-style container class, the first overload of IsContainerTest
// will be viable (since both C::iterator* and C::const_iterator* are
// valid types and NULL can be implicitly converted to them).  It will
// be picked over the second overload as 'int' is a perfect match for
// the type of argument 0.  If C::iterator or C::const_iterator is not
// a valid type, the first overload is not viable, and the second
// overload will be picked.
template<class C,
		 class Iterator = decltype(::std::declval<const C&>().begin()),
		 class = decltype(::std::declval<const C&>().end()),
		 class = decltype(++::std::declval<Iterator&>()),
		 class = decltype(*::std::declval<Iterator>()),
		 class = typename C::const_iterator>
bool
IsContainerType(int /* dummy */)
{
	return true;
}

template<class C>
bool
IsContainerType(long /* dummy */)
{
	return false;
}

template<typename Scalar, int Rows, int Cols>
void
test_stl_container_detection(int rows = Rows, int cols = Cols)
{
	typedef Matrix<Scalar, Rows, 1> VectorType;
	typedef Matrix<Scalar, Rows, Cols, ColMajor> ColMatrixType;
	typedef Matrix<Scalar, Rows, Cols, RowMajor> RowMatrixType;

	ColMatrixType A = ColMatrixType::Random(rows, cols);
	RowMatrixType B = RowMatrixType::Random(rows, cols);

	Index i = 1;

	using ColMatrixColType = decltype(A.col(i));
	using ColMatrixRowType = decltype(A.row(i));
	using RowMatrixColType = decltype(B.col(i));
	using RowMatrixRowType = decltype(B.row(i));

	// Vector and matrix col/row are valid Stl-style container.
	VERIFY_IS_EQUAL(IsContainerType<VectorType>(0), true);
	VERIFY_IS_EQUAL(IsContainerType<ColMatrixColType>(0), true);
	VERIFY_IS_EQUAL(IsContainerType<ColMatrixRowType>(0), true);
	VERIFY_IS_EQUAL(IsContainerType<RowMatrixColType>(0), true);
	VERIFY_IS_EQUAL(IsContainerType<RowMatrixRowType>(0), true);

	// But the matrix itself is not a valid Stl-style container.
	VERIFY_IS_EQUAL(IsContainerType<ColMatrixType>(0), rows == 1 || cols == 1);
	VERIFY_IS_EQUAL(IsContainerType<RowMatrixType>(0), rows == 1 || cols == 1);
}
#endif

EIGEN_DECLARE_TEST(stl_iterators)
{
	for (int i = 0; i < g_repeat; i++) {
		CALL_SUBTEST_1((test_stl_iterators<double, 2, 3>()));
		CALL_SUBTEST_1((test_stl_iterators<float, 7, 5>()));
		CALL_SUBTEST_1(
			(test_stl_iterators<int, Dynamic, Dynamic>(internal::random<int>(5, 10), internal::random<int>(5, 10))));
		CALL_SUBTEST_1((
			test_stl_iterators<int, Dynamic, Dynamic>(internal::random<int>(10, 200), internal::random<int>(10, 200))));
	}

#if EIGEN_HAS_CXX11
	CALL_SUBTEST_1((test_stl_container_detection<float, 1, 1>()));
	CALL_SUBTEST_1((test_stl_container_detection<float, 5, 5>()));
#endif
}
